The purpose of this invention is a process and device for identifying and localizing an area in relative movement in a scene and for determining the speed and oriented direction of this relative movement, in real time.
Relative movement means a movement of said area (which may be composed of an xe2x80x9cobjectxe2x80x9d in the broadest sense of the term including a living being or a portion of a living being, for example a hand) in an approximately motionless environment, or more or less complete immobility of said area (or xe2x80x9cobjectxe2x80x9d) in an environment that is at least partially in movement.
The invention relates to the processing of a digital video output signal from an observation system composed of an optical imput system or objective capable of forming an image of the observed scene, and by an optoelectronic conversion system or sensor capable of converting said image that it receives into a digital output signal.
In general, the observation system is composed of a video camera or camescope that observes the scene to be monitored (said digital output signal then being composed of the digital video signal output by a camera with a digital output or of the output of an analog/digital converter, the input of which is connected to the output of a camera outputting an analog video signal.
The observation system may also be composed of the objective of an optical instrument (binoculars, sighting refracting instrument, view-finder), from which at least a portion of the outgoing light beam is sampled and by a photoelectronic sensor, for example of the CCD or CMOS type, with the normal associated electronic system, sensor receiving the image formed by said portion of the light beam and converting it through the associated electronic system into a digital video output signal.
The invention consists mainly of processing the digital video output signal from an observation system, particularly a video camera, with a digital output to determine signals signaling the existence and localization of an area in relative movement in said scene, and the speed and oriented direction of the displacement if said area is actually moving in said scene relatively to an approximately motionless environment, in real time.
The best system yet developed for identifying and localizing an object in relative movement and for determining its speed and oriented direction of displacement is animal or human sight, for example a hunter in his hide localizing the displacement of an animal, and the direction and speed of this displacement.
Prior art surveillance devices like artificial retinas, either analog (Giocomo Indiveri et al, in Proceedings of MicroNeuro""96 pp 15 to 22), or digital (Pierre-Franxc3xa7ois Rxc3xcedi in Proceedings of MicroNeuro""96 pp 23 to 29), have been proposed, but the first article deals with detectors and analog units with complex structures, and the second article deals with means of identifying the edges of an object; furthermore, very fast and high capacity memories are used in the devices described in order to operate in real time, and limited information is obtained about moving areas or objects.
Thus the suggestion was made of memorizing a frame output signal from a video camera, or similar instrument, composed of a sequence of data relative to pixels representative of the scene observed by the camera at time t0 in a first two-dimensional memory, and then the video signal for the next corresponding frame representing said scene at time t1, in a second two-dimensional memory. If an object has moved between t0 and t1, on the one hand, the distance d by which the object has moved in the scene between t1 and t0 and, on the other hand, the time T=t1xe2x88x92t0 between the beginnings of two successive corresponding frames relative to the same pixels are determined. The displacement speed is then equal to d/T. This type of system requires a very large total memory capacity if it is required to obtain precise speed and oriented direction indications characterizing the displacement. Furthermore, there is some delay in obtaining the speed and displacement direction indications; this information is not available until time t1+R, where R is the time necessary for the calculations for the period t0xe2x88x92ti.These two disadvantages (the need for a large memory capacity and the delay in obtaining the required information) limit applications of this type of system.
Furthermore, French patent No. 2.611.063, of which one of the inventors (Mr. Patrick Pirim) is the inventor of the present invention, describes a process and a device for real time processing of a sequenced data flow, composed in particular of the output signal from a camescope, in order to perform data compression. According to this prior patent, the histogram of signal levels is formed using a classification law for a first sequence, the representative Gauss function associated with this histogram is memorized and the maximum and minimum levels are extracted from it, the levels of the next sequence or second sequence are compared with said signal levels for the first sequence memorized with a constant time constant identical for each pixel, a binary classification signal is generated that characterizes the next said sequence with reference to the classification law, an auxiliary signal is generated from this binary signal representative of the duration and position of a range of significant values, and finally said auxiliary signal is used to generate a signal localizing the range with the longest duration, called the dominant range, and these operations are repeated for subsequent sequences of the sequenced signal. This process and this device of classification enable data compression, keeping only interesting parameters in the processed flow of sequenced data. In particular, this process is capable of processing a digital video signal representative of a video image in order to extract and localize at least one characteristic of at least one area in said image. It is thus possible to classify brightness and/or chrominance levels of the signal and to characterize and localize an object in the image.
U.S. Pat. No. 5,488,430 detects and estimates a displacement by determining horizontal and vertical changes in the image of the observed area separately. Difference signals are used to detect movements from right to left or from left to right, or from top to bottom or bottom to top, in the horizontal and vertical directions respectively, firstly by carrying out the EXCLUSIVE OR logical function on horizontal/vertical difference signals and frame difference signals, and secondly by using a ratio of the sums of horizontal/vertical signals and the sums of frame difference signals with respect to a Kxc3x973 window. In this U.S. Pat. No. 5,488,430, calculated values of the image along two orthogonal horizontal and vertical directions are used with an identical repetitive difference K in these two orthogonal directions, this difference K being defined as a function of the displacement speeds that are to be determined. The device according to this US patent determines the direction of movements along each of the two orthogonal directions by applying a set of calculation operations indicated in columns 12 (at the beginning and end) and 13 (at the beginning) to the difference signals, which requires very complex (and therefore difficult to execute) electronic computing units performing particularly division, multiplication and summation; furthermore, additional complex computing units are necessary to obtain the speed and oriented direction of displacement (extraction of square root to obtain the amplitude of the speed and calculation of the arc tan function to obtain the oriented direction), starting from projections on the two horizontal and vertical axes. Finally U.S. Pat. No. 5,488,430 does not include any means of smoothing pixel values by means of a time constant, variable for each pixel, in order to compensate for excessively fast variations of these values.
On the contrary, the process according to the invention is embodied by using a digital type of device, object of the invention, which has a relatively simple structure and a relatively small memory capacity, and by which the required information can be obtained quickly with a wide variety of results and applications (corresponding to a complete half-image for interlaced frames or a complete image, depending on the application).
An article by Alberto Tomita Sr. and Rokuya Ishii, entitled xe2x80x9cHand Shape Extraction from a Sequence of Digitized Gray-Scale Imagesxe2x80x9d in Institute of Electrical and Electronics Engineers, vol. 3, 1994, p 1925-1930, implements a movement detection by subtraction between successive images followed by the formation of histograms based on the shape of a human hand in order to extract the shape of a human hand in a digitized scene. The histogram analysis is based on a gray scale inherent to the human hand. It does not include any means of forming histograms of the plane coordinates. The sole purpose of the authors of this article is to detect the displacements of a human hand, for example in order to replace the normal mouse by a hand, the displacements of which are identified, for inputting data into a computer.
On the contrary, the present invention is not limited to detecting the displacement of a hand, but is capable of detecting the relative displacement of any object (in the widest sense of the term) in a scene, and does not use histograms based on the gray values of a hand, but rather the histograms of some particular digital variables representative of the displacement (if any) and histograms of plane coordinates.
According to this invention:
a digital video output signal from an observation system is processed, this signal being composed of a sequence of frames (corresponding to a half-image in the case of two interlaced frames per image or to a complete image in the case of a single frame per image) in the known manner, each consisting of a given number of successive lines, and a given number of pixels or image points in each of these lines,
in order to obtain, using a relatively small memory capacity, signals capable of indicating if there is an area in relative movement in the observed scene and, if so, to specify the localization, and speed and oriented direction of said area if it is actually moving with respect to its environment,
by generating two digital signals, one characteristic of the significant variation or non-variation of the pixel signal, for the same pixel location, between two successive corresponding frames, and the other characteristic of the amplitude of this variation, if any, and performing a matrix distribution of these two signals for the pixels in a portion of a frame at a same instant.
It is a first object of the invention to provide a process operating in real time for identifying and localizing an area in relative movement in a scene observed by an observation system with an output constituted by a digital video signal of the type comprising a succession of corresponding frames, each composed of a succession of lines, each composed of a succession of pixels, and for determining the speed and oriented direction of the displacement, said process being characterized in that it consists in carrying out the following sequence of operations on the digital video output signal:
a smoothing processing on said digital video output signal using a digital time constant, the numerical value of which may be modified independently for each pixel of said output signal,
a memorization, on the one hand, of a frame of said output signal after smoothing and, on the other hand, of the smoothing time constant associated with said frame,
a temporal processing for each pixel position, consisting in determining firstly the existence, and secondly the amplitude of a significant variation in the amplitude of the pixel signal between the current frame and the immediately preceding smoothed and memorized frame, and generating two digital signals, the first signal being a binary, or single bit, signal with two possible values, one of which represents the presence and the other represents the absence of a significant variation between two successive frames, the value of said binary signal modifying the memorized value of said time constant in order to reduce it if said signal represents a significant variation and in order to increase it if said signal does not represent such a variation, the reduction or increase being done in a quantified manner, whereas the second digital signal, i.e. the amplitude signal, is a multibit signal with a limited number of bits quantifying the amplitude of this variation; and
a spatial processing consisting of the following steps for each frame of the digital video input signal:
distributing only the values of a fraction of the pixels in a frame at a given observation instant (a fraction which is scanned across said matrix throughout the duration of the frame) firstly of said binary signal and secondly of said digital amplitude signal, into a matrix with a number of rows and columns that is small compared with the number of lines and the number of pixels per line in the video signal, respectively, in order to characterize the values of the pixels,
determining in this double instantaneous matrix representation, a particular area in which said binary signal has the value sought for, representing the presence or absence of a significant variation, and said digital amplitude signal varies, or does not vary, by a significant value for adjacent pixels in the matrix along an oriented direction starting from an origin pixel, within the same portion of the frame and therefore at the same observation instant, and
generating signals representing the existence and localization of the area in relative displacement and the relative inter-frame speed and the oriented direction of this displacement, if any, relative to its environment, inferred from the instantaneous matrix distribution of these two binary and amplitude digital signals.
Preferably, the process according to the invention is characterized in that it also consists of:
forming firstly histograms of the signal values distributed in matrices, and secondly histograms of the inclinations of two coordinate axes, with variable slope, in a plane,
identifying a domain in which there is a significant variation of the processed values in each histogram formed, and
for each identified domain, deducing whether or not there is an area in relative movement, and if so its localization, speed and oriented direction.
In specific embodiments:
said matrix is a square matrix with the same odd number of rows and columns (2l+1), and nested matrices containing 3xc3x973, 5xc3x975, 7xc3x977, . . . (2l+1)xc3x97(2l+1) elements, centered on the center of this square matrix, are considered in order to determine the smallest nested matrix in which said digital signal varies along an oriented direction starting from said center, the value of said binary signal showing that the threshold limit along this direction has been exceeded,
said matrix is a hexagonal matrix, and nested hexagonal matrices of increasing size, centered on the center of this hexagonal matrix, are considered, in order to determine the smallest nested matrix in which said digital signal varies along an oriented direction,
said matrix is an inverted L matrix with a single row and a single column, and nested matrices containing 3xc3x973 pixels, 5xc3x975 pixels, 7xc3x977 pixels, . . . (2l+1)xc3x97(2l+1) pixels are considered for the single row and the single column, in order to determine the smallest matrix in which the signal varies along an oriented direction, namely the line with the steepest slope and constant quantification.
Advantageously, said time constant is of the form 2p, where p is a number less than 16, and which can then be expressed in not more than 4 bits, the time constant being reduced or increased by subtracting or adding one unit to p.
In this case, if it is required, successive decreasing portions of complete frames are considered using the Mallat time-scale algorithm and the largest of these portions, which gives displacement, speed and orientation indications compatible with the value of p, is selected.
Another object of the invention is a device operating in real time for identifying and localizing an area in relative movement in a scene observed by an observation system with an output constituted by a digital video signal of the type comprising a succession of corresponding frames, successive lines in each corresponding frame and successive pixels in each line, and for determining the speed and oriented direction of the displacement, by using the process described above, said device receiving said video output signal as input and being characterized in that it comprises in combination:
means for smoothing said digital video output signal making use of a digital time constant, the numerical value of which may be modified independently for each of said output signal pixels;
means for memorizing firstly a frame of said output signal after smoothing and secondly the smoothing time constant associated with said frame,
a temporal processing unit to analyze the variations with time of the amplitude of the pixel signal, for the same pixel position, between the current frame and the immediately preceding smoothed and memorized frame of said digital signal, said unit comprising a memory capable of receiving, storing and retrieving information about the corresponding previous smoothed frame, together with means of comparison to determine if the absolute value of the difference, between the current pixel signal and a representative value of the pixel signal for the same pixel position in the previous frame stored in said memory, exceeds or does not exceed a threshold, for each position of the pixel in the input video signal frame, by generating a binary, or single bit, signal with two values, one of these two values showing that the threshold is exceeded and the other showing that it is not exceeded, and computing means capable of determining a multibit digital amplitude signal with a small number of bits, the value of which depends on the amplitude of the variation in the value of the same pixel between the current frame and the immediately preceding, smoothed and memorized, frame of the digital video signal; and
a spatial processing unit, into which the outputs from said successive binary and digital amplitude signals for the pixels in a given frame produced by the temporal processing unit are input, said spatial processing unit comprising means for characterizing the amplitude values of the pixels, these means distributing only said binary and digital amplitude signals relative to the same instant, i.e. to a single frame, into a matrix with fewer rows and columns than the number of lines and the number of pixels per line respectively in a frame of said digital video signal, the frame being scanned across said matrix throughout the duration of a frame, spotting means for determining an area of pixels within said matrix in which, at this instant, the binary signal has the searched value, and means of determining an area of pixels in said matrix, into which, at the same instant, the digital amplitude signal for adjacent pixels varies by a significant quantity, and means which, in response to the indications from the two preceding means, generate signals representing this area of pixels and therefore the existence and localization of an area in relative movement within the observed scene and the relative inter-frame speed and oriented direction of this area when it actually moves relative to its environment.
Preferably, the spatial processing unit will also include an output delivering a delayed digital video signal consisting of the input digital video signal with a delay equal to the duration of the rows of a matrix minus the duration of a row, in order to supply an output signal contemporary with the analysis of the matrix in said temporal processing unit.
Preferably, the spatial processing unit of the device according to the invention, includes delay means in cascade, each of which imposes a delay equal to the time difference between the beginning of two successive lines, and delay means in cascade for each line, each importing a delay equal to the time difference between two successive pixels in a line, the outputs from all registers and the input to the first registers on each line delivering at a given instant the values of said binary signal and said digital amplitude signal at the same instant, to said identification means.
Advantageously, the device according to the invention also comprises means for forming histograms of the output values from said spatial processing unit, and histograms of the inclinations of two, variable slope, coordinate axes within a plane, means for identifying a domain, in each histogram, in which there is a significant variation in the processed value, in order to validate this domain at their output, and to deduce, for all histograms, output signals that identify and localize an area of relative movement in the observed scene, if any, and the speed and oriented direction of this movement if said area is effectively moving with respect to its environment.
If it is required to detect the movement of an object in an approximately motionless environment, it is necessary to determine the part of the matrix in which the value of the binary signal shows that the limit has been exceeded and at the same time the digital amplitude signal varies by a significant value between adjacent pixels in a frame.
On the contrary, if it is required to detect a motionless object in an environment that is effectively in motion, it is necessary to determine the part of the matrix in which the value of the binary signal shows that the limit has not been exceeded and at the same time the digital amplitude signal does not vary between adjacent pixels in a frame.
Preferably in the device for identifying, localizing and determining the speed and oriented direction of displacement of an area in relative movement
in a scene, embodying the above mentioned process: said smoothing means include an input receiving said digital video signal and derive, for each successive pixel in a frame of said video signal, a smoothed signal in which the temporal variations of the input digital video signal are reduced by using a threshold signal received on another input and a time constant related to each pixel position in a frame, the value of which is modified successively so that the smoothing maintains, although reduced, the trend in the variations of the incoming digital video signal, said smoothing means working in cooperation with said memory unit that receives, stores and retrieves the updated values of the smoothed signal and of said time constant, for each portion of pixels in a frame, and output, for each pixel position, at least the succession of values of the updated time constant and of the values of the binary signal that shows whether or not said threshold is exceeded by the absolute value of the difference between the value of the pixel and its smoothed value; said spatial processing assembly carrying out the matrix distribution along lines and columns in a reduced number, of the outputs from said smoothing means, namely the successive values of the time constant and of said binary signal;
means are provided for identifying, in said matrix distribution, an area of pixels in which simultaneously:
either the value of said binary signal corresponds to a threshold being exceeded and said time constant varies between adjacent pixels by a significant value in one direction and for producing output signals indicating the localization of said area and the speed and oriented direction of displacement in this area
or the value of said binary signal corresponds to a limit not being exceeded and said time constant does not vary between adjacent pixels and for producing output signals indicating the localization of said area.
In the preferred embodiments:
said smoothing means include, in combination with a video memory or field memory that stores successive values, for each pixel in the frame, of said time constant and the smoothed digital video signal, means for calculating, for each pixel, the absolute value of the difference between the value of the digital video signal output from the camera and the value of the previously smoothed digital video signal, means for comparing said difference with a threshold, and for generating a binary signal, one of the two values of which indicates that said limit has been exceeded and the other value indicates that it has not been exceeded; means for updating the time constant receiving the immediately preceding value of the time constant from said memory and reducing it if it receives a binary signal with a value showing that the limit has been exceeded, or increase it if the value of the binary signal indicates that it has not been exceeded, the reduction or increase being however not performed if it would lead respectively to a negative value or to a value exceeding a threshold value, and means for updating the smoothed value of the digital video signal that algebraically add, to the prior value of this smoothed signal received from said memory, the quotient of the difference between the digital video signal output from the camera and the previous smoothed digital video signal from said memory by a factor equal to value of the previous time constant retrieved by from said memory;
said time constant is in the form 2p, where p is an integer less than 16, and which can therefore be represented by not more than 4 bits, the reduction or increase in the time constant being done by subtracting or adding one unit to p;
said matrix distribution means include in combination with delay means applying successive delays, equal to the duration of one line of the video signal, to the digital video signal originating from the camera so as to deliver on successive outputs this video signal delayed by one delay period, two delay periods and so on, up to a number of delay periods equal to the number of lines in the spatial distribution matrix minus one, means for performing a matrix distribution along successive rows of the matrix receiving firstly, the digital video signal from the camera without a delay and this progressively delayed signal output from the delaying means outputs and secondly, values of the time constant and said binary signal received from said smoothing means in order for producing a matrix distribution, in rows and columns, of said values, at a given instant, of the time constant and binary signal for pixels in a portion of the frame of the digital video signal with the same size as the matrix;
the matrix distribution means comprise a series of digital signal conductors, i.e. one for each row in the distribution matrix, each with series-connected shift registers, each imposing a delay equal to the time difference between two successive pixels in a line of the digital video signal, the position of a pixel distributed in the matrix being determined by a point in the matrix located before a delay register, the number per line thereof being equal to the number of columns in the matrix minus one, and by a point downstream the furthest downstream register;
said means of detecting a moving area in said matrix, by detecting the simultaneous presence of a value of the binary signal indicating that a limit was exceeded and a variation in the value of the time constant, include means for determining, along discrete digitized oriented directions, the slope of the variation in the value of the time constant close to a pixel at the center of said matrix, forming the origin for said directions, and means for selecting the steepest slope of this variation close to this center-origin and determining the oriented direction, taking account of a selection criterion for selecting the direction if there is more than one direction with same maximum slope of this variation, these latter means outputting signals representative of the speed and oriented direction of the displacement in the moving area, with a validation signal indicating that these speed and direction signals are validated, together with the value of the time constant.
Preferably, if included in the device according to the invention, the means for creating the histograms each include:
inputs receiving the signal from which the histogram is formed and a validation signal originating from the matrix distribution means; and
means for establishing two linear unidimensional histograms for the two plane coordinates and for combining these two linear histograms into a surface histogram representing the area in which there is a significant variation in the input signal, and
an output delivering a signal representative of said area.
Furthermore, the means for forming the histograms preferably include:
means for calculating a reference change, the inputs of which receive a line sequence signal, a column sequence signal and a pixel clock signal and the output of which is representative of the reference change;
two means for forming histograms for two axes, receiving the two reference signals and forming histograms of these axes; and
area means into which the outputs from the two histogram formation means for the two axes are input, and which output a signal containing global slope information for the two axes.
In some applications, said time constant may be composed of the order number of the intervals, in limited number and with a gradually increasing magnitude, into which the absolute value of the difference between the value of the current pixel and the immediately preceding value of the same pixel after smoothing is divided, for each pixel position.
Advantageously, for determining the binary signal of overshooting, or not overshooting, of the threshold the absolute value of the difference between the value of the current input pixel and the immediately preceding smoothed value of the same pixel originating from the memory in compared with a threshold value, for each pixel position.
As concerns the digital amplitude signal, it is preferably generated as an integer representing the tendency of the value of the current pixel to approach the immediately preceding smoothed value of this pixel, for each pixel position.
One of the characteristics of the invention consists of the fact that, for determining both the binary signal and the digital amplitude signal, use is made, as value of the immediately preceeding pixel, of a stored smoothed value thereof, in order to reduce any excessive variations of this pixel signal with time that may exist in the digital video input signal originating from the video camera or any other observation device with a digital output.
It is known that the effect of a smoothing operation is to gradually substitute, for a digital signal with large amplitude variations with time, a signal with smaller variations and therefore more easily quantifiable with a small number of steps, and therefore bits, in the smoothed digital amplitude signal.
We will now describe a preferred embodiment, given for illustrative purposes and in no way limitative, of a device according to the invention embodying the process according to the invention, with reference to the appended drawings.